package ua.mykola.bit;

public class BitCounter
{
    private int precomputedBits;

    private int precomputedSize;

    private int[] precomputed;

    public int countOnes(int k)
    {
        int count = 0;
        for (; k != 0; k >>>= 1)
        {
            count += k & 1;
        }
        return count;
    }

    public int countSparseOnes(int k)
    {
        int count = 0;
        while (k != 0)
        {
            count++;
            k &= k - 1;
        }
        return count;
    }

    public int countDenseOnes(int k)
    {
        int count = 32;
        k = ~k;
        while (k != 0)
        {
            count--;
            k &= k - 1;
        }
        return count;
    }

    public void precompute(int bits)
    {
        precomputedBits = bits;
        precomputedSize = 1 << bits;
        precomputed = new int[precomputedSize];
        for (int i = 0; i < precomputedSize; i++)
        {
            precomputed[i] = countOnes(i);
        }
    }

    public int countOnesWithPrecomputation(int k)
    {
        int count = 0;
        for (; k != 0; k >>>= precomputedBits)
        {
            count += precomputed[k & (precomputedSize - 1)];
        }
        return count;
    }
}
